{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find K-Length Substrings With No Repeated Characters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #string #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #字符串 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numKLenSubstrNoRepeats"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #长度为 K 的无重复字符子串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串&nbsp;<code>S</code>，找出所有长度为&nbsp;<code>K</code>&nbsp;且不含重复字符的子串，请你返回全部满足要求的子串的&nbsp;<strong>数目</strong>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>S = &quot;havefunonleetcode&quot;, K = 5\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>\n",
    "这里有 6 个满足题意的子串，分别是：&#39;havef&#39;,&#39;avefu&#39;,&#39;vefun&#39;,&#39;efuno&#39;,&#39;etcod&#39;,&#39;tcode&#39;。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>S = &quot;home&quot;, K = 5\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>\n",
    "注意：K 可能会大于 S 的长度。在这种情况下，就无法找到任何长度为 K 的子串。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li><code>1 &lt;= S.length &lt;= 10^4</code></li>\n",
    "\t<li><code>S</code> 中的所有字符均为小写英文字母</li>\n",
    "\t<li><code>1 &lt;= K &lt;= 10^4</code></li>\n",
    "</ol>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-k-length-substrings-with-no-repeated-characters](https://leetcode.cn/problems/find-k-length-substrings-with-no-repeated-characters/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-k-length-substrings-with-no-repeated-characters](https://leetcode.cn/problems/find-k-length-substrings-with-no-repeated-characters/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"havefunonleetcode\"\\n5', '\"home\"\\n5']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        ans = 0\n",
    "        r,l = 0,0\n",
    "        cur = ''\n",
    "        while r<len(s):\n",
    "            cur += s[r]\n",
    "            if r-l+1>=k:\n",
    "                if len(set(cur))==k:\n",
    "                    ans += 1\n",
    "                cur =cur[1:]\n",
    "                l+= 1\n",
    "            r += 1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "      if k > 26 or len(s) < k:  return 0\n",
    "      flag = collections.Counter(s[:k])\n",
    "      cnt = 0\n",
    "      if len(flag) == k:  cnt += 1\n",
    "      for i in range(k, len(s)):\n",
    "        flag[s[i-k]] -= 1\n",
    "        if flag[s[i-k]] == 0: del flag[s[i-k]]\n",
    "        flag[s[i]] += 1\n",
    "        if len(flag) == k:  cnt += 1\n",
    "      return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        max_s,hashmap=0,{}\n",
    "        start=0\n",
    "        for i in range(len(s)):\n",
    "            hashmap[s[i]]=hashmap.get(s[i],0)+1\n",
    "            while hashmap[s[i]]>1:\n",
    "                hashmap[s[start]]-=1\n",
    "                if hashmap[s[start]]==0:\n",
    "                    del hashmap[s[start]]\n",
    "                start+=1\n",
    "            if len(hashmap)>=k:\n",
    "                max_s+=1\n",
    "        return max_s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        left,res,n = 0,0,len(s)\n",
    "        if k>n: return 0\n",
    "        cnt = collections.Counter(s[:k])\n",
    "        for right in range(k,n):\n",
    "            if len(cnt)==k:res+=1\n",
    "            cnt[s[right]]+=1\n",
    "            cnt[s[left]]-=1\n",
    "            if cnt[s[left]]==0:\n",
    "                cnt.pop(s[left])\n",
    "            left+=1\n",
    "        if len(cnt)==k:res+=1\n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        if n < k: return 0\n",
    "        res = 0\n",
    "        window = [0 for _ in range(26)]\n",
    "        for i in range(k):\n",
    "            window[ord(s[i]) - ord('a')] += 1\n",
    "        if max(window) == 1:\n",
    "            res += 1\n",
    "        for i in range(k, n):\n",
    "            window[ord(s[i]) - ord('a')] += 1\n",
    "            window[ord(s[i-k]) - ord('a')] -= 1\n",
    "            if max(window) == 1:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        res = 0\n",
    "        for i in range(len(s) - k + 1):\n",
    "            if len(set(s[i: i + k])) == k:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        if n < k:\n",
    "            return 0\n",
    "\n",
    "\n",
    "        ret = 0\n",
    "        i = 0\n",
    "        buf = set()\n",
    "        for j in range(n):\n",
    "            c = s[j]\n",
    "            while c in buf or len(buf) >= k:\n",
    "                buf.remove(s[i])\n",
    "                i += 1\n",
    "            buf.add(c)\n",
    "            if len(buf) == k:\n",
    "                ret += 1\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        if k > 26:\n",
    "            return 0\n",
    "        words = [0]*26\n",
    "        left = right = 0\n",
    "        res = 0\n",
    "        while right < len(s):\n",
    "            index = ord(s[right]) - ord('a')\n",
    "            words[index] += 1\n",
    "\n",
    "            while words[index] > 1:                \n",
    "                words[ord(s[left]) - ord('a')] -= 1\n",
    "                left += 1\n",
    "            \n",
    "            if right - left + 1 == k:\n",
    "                res += 1\n",
    "                words[ord(s[left]) - ord('a')] -= 1\n",
    "                left += 1\n",
    "            \n",
    "            right += 1\n",
    "        return res\n",
    "\n",
    "        \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        if k > 26:\n",
    "            return 0\n",
    "        \n",
    "        result = 0\n",
    "        n = len(s)\n",
    "        left = right = 0\n",
    "        freq = [0] * 26\n",
    "\n",
    "        while right < n:\n",
    "            freq[ord(s[right]) - ord('a')] += 1\n",
    "\n",
    "            while freq[ord(s[right]) - ord('a')] > 1:\n",
    "                freq[ord(s[left]) - ord('a')] -= 1\n",
    "                left += 1\n",
    "            \n",
    "            if right - left + 1 == k:\n",
    "                result += 1\n",
    "                freq[ord(s[left]) - ord('a')] -= 1\n",
    "                left += 1\n",
    "            \n",
    "            right += 1\n",
    "        \n",
    "        return result\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        pos = {}\n",
    "        l = r = 0\n",
    "        count = 0\n",
    "        while (r < len(s)):\n",
    "            if s[r] not in pos:\n",
    "                pos[s[r]] = r\n",
    "            else:\n",
    "                # 删除l到pos[S[r]]的元素信息\n",
    "                start = pos[s[r]] + 1\n",
    "                for i in range(l, pos[s[r]] + 1):\n",
    "                    del pos[s[i]]\n",
    "                l = start\n",
    "                pos[s[r]] = r\n",
    "\n",
    "            if len(pos) == k:\n",
    "                count += 1\n",
    "                del pos[s[l]]\n",
    "                l += 1\n",
    "            r += 1\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # Moving window. Time O(n) Space O(1)\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        if n < k: return 0\n",
    "        res = 0\n",
    "        window = [0 for _ in range(26)]\n",
    "        for i in range(k):\n",
    "            window[ord(s[i]) - ord('a')] += 1\n",
    "        if max(window) == 1:\n",
    "            res += 1\n",
    "        for i in range(k, n):\n",
    "            window[ord(s[i]) - ord('a')] += 1\n",
    "            window[ord(s[i-k]) - ord('a')] -= 1\n",
    "            if max(window) == 1:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "      if k > 26 or len(s) < k:  return 0\n",
    "      flag = collections.Counter(s[:k])\n",
    "      cnt = 0\n",
    "      if len(flag) == k:  cnt += 1\n",
    "      for i in range(k, len(s)):\n",
    "        flag[s[i-k]] -= 1\n",
    "        if flag[s[i-k]] == 0: del flag[s[i-k]]\n",
    "        flag[s[i]] += 1\n",
    "        if len(flag) == k:  cnt += 1\n",
    "      return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        length = len(s)\n",
    "        ans = 0\n",
    "        if k > length:\n",
    "            return 0\n",
    "        for i in range(length - (k-1)):\n",
    "            if len(Counter(s[i:i+k])) == k:\n",
    "                ans += 1\n",
    "            else:\n",
    "                continue\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        s_len = len(s)\n",
    "        if k > s_len:\n",
    "            return 0\n",
    "\n",
    "        left = right = result = 0\n",
    "\n",
    "        storage = collections.defaultdict(int)\n",
    "\n",
    "        while right < s_len:\n",
    "            storage[s[right]] += 1\n",
    "\n",
    "            while storage[s[right]] == 2:\n",
    "                storage[s[left]] -= 1\n",
    "\n",
    "                if storage[s[left]] == 0:\n",
    "                    del storage[s[left]]\n",
    "                left += 1\n",
    "\n",
    "            if len(storage) >= k:\n",
    "                result += 1\n",
    "\n",
    "            right += 1\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        res = 0\n",
    "        for i in range(len(s) + 1 - k):\n",
    "            if len(set(s[i: i + k])) == k:\n",
    "                res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        # if len(s) < k:\n",
    "        #     return 0\n",
    "        # c = 0\n",
    "        # for i in range(len(s)-k+1):\n",
    "        #     sub = s[i:i+k]\n",
    "        #     cc = [sub.count(sub[j]) for j in range(k)]\n",
    "        #     # print(max(cc))\n",
    "        #     if max(cc) > 1:\n",
    "        #         continue\n",
    "        #     else: c +=1\n",
    "        #     # a=0\n",
    "        # # print(s[i:i+k])\n",
    "        # return c\n",
    "        if k>26:\n",
    "            return 0\n",
    "        answer = 0\n",
    "        n =len(s)\n",
    "\n",
    "        for i in range(n-k+1):\n",
    "            freq=[0]*26\n",
    "\n",
    "            for j in range(i, i+k):\n",
    "                curr_char = ord(s[j]) - ord('a')\n",
    "                freq[curr_char] +=1\n",
    "                if freq[curr_char] >1:\n",
    "                    break\n",
    "            else:\n",
    "                answer +=1\n",
    "        return answer\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        cnt=Counter()\n",
    "        for c in s[:k-1]:\n",
    "            cnt[ord(c)]+=1\n",
    "        ans=0\n",
    "        for _in,out in zip(s[k-1:],s):\n",
    "            cnt[ord(_in)]+=1\n",
    "            if len(cnt)==k:\n",
    "                ans+=1\n",
    "            cnt[ord(out)]-=1\n",
    "            if cnt[ord(out)]==0:\n",
    "                del cnt[ord(out)]\n",
    "        return ans\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        l = len(s)\n",
    "        if l < k:\n",
    "            return 0\n",
    "        \n",
    "        hashmap = {}\n",
    "        count = 0\n",
    "        left = right = 0\n",
    "        while right < l:\n",
    "            if s[right] not in hashmap:\n",
    "                hashmap[s[right]] = 1\n",
    "            else:\n",
    "                hashmap[s[right]] += 1\n",
    "            while hashmap[s[right]] > 1:\n",
    "                hashmap[s[left]] -= 1\n",
    "                if hashmap[s[left]] == 0:\n",
    "                    del hashmap[s[left]]\n",
    "                left += 1\n",
    "            if right - left + 1 >= k:\n",
    "                count += 1\n",
    "            right += 1\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        ans = 0\n",
    "        vis = set()\n",
    "        j = 0\n",
    "        for i, x in enumerate(s):\n",
    "            while x in vis:\n",
    "                vis.remove(s[j])\n",
    "                j += 1\n",
    "            vis.add(x)\n",
    "            if len(vis) > k:\n",
    "                vis.remove(s[j])\n",
    "                j += 1\n",
    "            if len(vis) == k:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        if k > len(s):\n",
    "            return 0\n",
    "\n",
    "        exist = defaultdict(int)\n",
    "        curr_char = 0\n",
    "        res = 0\n",
    "\n",
    "        for i in range(k):\n",
    "            if exist[s[i]] == 0:\n",
    "                curr_char += 1\n",
    "            exist[s[i]] += 1\n",
    "        \n",
    "        if curr_char == k:\n",
    "            res += 1\n",
    "\n",
    "        for i in range(len(s) - k):\n",
    "            if exist[s[i]] == 1:\n",
    "                curr_char -= 1\n",
    "            exist[s[i]] -= 1\n",
    "            if exist[s[k + i]] == 0:\n",
    "                curr_char += 1\n",
    "            exist[s[k + i]] += 1\n",
    "            if curr_char == k:\n",
    "                res += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "      if k > 26 or len(s) < k:  return 0\n",
    "      flag = collections.Counter(s[:k])\n",
    "      cnt = 0\n",
    "      if len(flag) == k:  cnt += 1\n",
    "      for i in range(k, len(s)):\n",
    "        flag[s[i-k]] -= 1\n",
    "        if flag[s[i-k]] == 0: del flag[s[i-k]]\n",
    "        flag[s[i]] += 1\n",
    "        if len(flag) == k:  cnt += 1\n",
    "      return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        left=right=0\n",
    "        seq_len = len(s)\n",
    "        slide_win = set()\n",
    "        result = 0\n",
    "        while right < seq_len:\n",
    "            if s[right] not in slide_win and len(slide_win) < k:\n",
    "                slide_win.add(s[right])\n",
    "                if len(slide_win) == k:\n",
    "                    result += 1\n",
    "                right += 1\n",
    "            else:\n",
    "                slide_win.remove(s[left])\n",
    "                left += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        if n < k:\n",
    "            return ans\n",
    "        # 双指针\n",
    "        d1, d2 = defaultdict(int), defaultdict(int)\n",
    "        for i in range(k):\n",
    "            d2[s[i]] += 1\n",
    "        for i in range(k, n + 1):\n",
    "            flag = True\n",
    "            for j in range(26):\n",
    "                if d2[chr(ord('a') + j)] - d1[chr(ord('a') + j)] >= 2: # 重复了\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag:\n",
    "                ans += 1\n",
    "            if i == n:\n",
    "                break\n",
    "            #print(i)\n",
    "            d2[s[i]] += 1\n",
    "            d1[s[i - k]] += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        l, r = 0, k-1\n",
    "        ans = 0\n",
    "\n",
    "        while r < len(s):\n",
    "            if len(set(s[l:r+1])) == k:\n",
    "                ans +=1\n",
    "            r +=1\n",
    "            l += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        if k > 26:\n",
    "            return 0\n",
    "        n = len(s)\n",
    "        count = 0\n",
    "        left = 0\n",
    "        dp = [0]*26\n",
    "        for i in range(n):\n",
    "            dp[ord(s[i])-ord('a')] += 1\n",
    "            while dp[ord(s[i])-ord('a')] > 1:\n",
    "                dp[ord(s[left])-ord('a')] -= 1\n",
    "                left += 1\n",
    "            if i-left+1 == k:\n",
    "                count += 1\n",
    "                dp[ord(s[left])-ord('a')] -= 1\n",
    "                left += 1\n",
    "            \n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        if k==1:\n",
    "            return len(s)\n",
    "        res=0\n",
    "        l=0\n",
    "        d={}\n",
    "        for i in range(len(s)):\n",
    "            if s[i] in d:\n",
    "                while s[l]!=s[i]:\n",
    "                    del d[s[l]]\n",
    "                    l+=1\n",
    "                l+=1\n",
    "                if i-l==k:\n",
    "                    res+=1\n",
    "                d[s[i]]=i\n",
    "            elif i-l+1<k:\n",
    "                d[s[i]]=i\n",
    "            else:\n",
    "                del d[s[l]]\n",
    "                l+=1\n",
    "                res+=1\n",
    "                d[s[i]]=i\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        n=len(s)\n",
    "        if n<k:\n",
    "            return 0\n",
    "        if k==1:\n",
    "            return n\n",
    "        slow=0\n",
    "        fast=1\n",
    "        ans=0\n",
    "        cnt=1\n",
    "        visited=set()\n",
    "        visited.add(s[slow])\n",
    "        while slow<n:\n",
    "            # print(slow,fast,visited)\n",
    "            while fast<n and s[fast] not in visited:\n",
    "\n",
    "                visited.add(s[fast])\n",
    "                # print(visited,cnt)\n",
    "                cnt+=1\n",
    "                fast+=1\n",
    "                if cnt==k:\n",
    "                    ans+=1\n",
    "                    break\n",
    " \n",
    "            slow+=1\n",
    "            fast=slow+1\n",
    "            visited=set()\n",
    "            cnt=1\n",
    "            if slow<n:\n",
    "                visited.add(s[slow])\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        \n",
    "        len_s = len(s)\n",
    "        if len_s < k:\n",
    "            return 0\n",
    "        \n",
    "        start = 0\n",
    "        end = 0\n",
    "        char2pos = {}\n",
    "        ans = 0\n",
    "        \n",
    "        while end < len_s:\n",
    "            \n",
    "            if end - start == k:\n",
    "                ans += 1 \n",
    "                char2pos.pop(s[start])\n",
    "                start += 1\n",
    "            \n",
    "            if s[end] not in char2pos:\n",
    "                char2pos[s[end]] = end\n",
    "                \n",
    "            else:\n",
    "                next_start = char2pos[s[end]] + 1\n",
    "                [char2pos.pop(s[index]) for index in range(start, next_start)]\n",
    "                start = next_start\n",
    "                char2pos[s[end]] = end\n",
    "            \n",
    "            end += 1\n",
    "        \n",
    "        return ans + int(end - start == k)\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        if k > len(s): return 0\n",
    "\n",
    "        res = 0\n",
    "        hs = {}\n",
    "\n",
    "        l = 0\n",
    "        r = k-1\n",
    "\n",
    "        def check(ss):\n",
    "            return true\n",
    "\n",
    "        i = 0\n",
    "        while i < k:\n",
    "            if s[i] not in hs:\n",
    "                hs[s[i]] = 1\n",
    "            else:\n",
    "                hs[s[i]] +=1\n",
    "            i+=1\n",
    "\n",
    "        while r < len(s):\n",
    "            if len(hs) == k: res+=1\n",
    "            if hs[s[l]] == 1:\n",
    "                del hs[s[l]]\n",
    "            else:\n",
    "                hs[s[l]] -=1\n",
    "\n",
    "            l+=1\n",
    "            r+=1\n",
    "            if r >= len(s): break\n",
    "\n",
    "            if s[r] in hs:\n",
    "                hs[s[r]] +=1\n",
    "            else:\n",
    "                hs[s[r]] =1\n",
    "\n",
    "        return res\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        s_len = len(s)\n",
    "\n",
    "        if s_len < k:\n",
    "            return 0\n",
    "\n",
    "        left = right = result = 0\n",
    "\n",
    "        counter = collections.defaultdict(int)\n",
    "\n",
    "        while right < s_len:\n",
    "            right_num = s[right]\n",
    "            counter[right_num] += 1\n",
    "\n",
    "            while counter[right_num] == 2:\n",
    "                left_num = s[left]\n",
    "                counter[left_num] -= 1\n",
    "                if counter[left_num] == 0:\n",
    "                    del counter[left_num]\n",
    "                left += 1\n",
    "\n",
    "            if len(counter) >= k:\n",
    "                result += 1\n",
    "\n",
    "            right += 1\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        if n < k:\n",
    "            return 0\n",
    "\n",
    "\n",
    "        ret = 0\n",
    "        i = 0\n",
    "        buf = set()\n",
    "        for c in s:\n",
    "            while c in buf or len(buf) >= k:\n",
    "                buf.remove(s[i])\n",
    "                i += 1\n",
    "            buf.add(c)\n",
    "            if len(buf) == k:\n",
    "                ret += 1\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        d = collections.defaultdict(int)\n",
    "        l = ret = 0\n",
    "        for r in range(len(s)):\n",
    "            c = s[r]\n",
    "            if c in d and d[c] + 1 > l:\n",
    "                l = d[c] + 1\n",
    "            \n",
    "            while r - l + 1 > k:\n",
    "                l += 1\n",
    "\n",
    "            if r - l + 1 == k:\n",
    "                #print(f\"{l} {r}\")\n",
    "                ret += 1\n",
    "\n",
    "            d[c] = r\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        res = 0\n",
    "        for i in range(len(s) + 1 - k):\n",
    "            if len(set(s[i: i + k])) == k:\n",
    "                res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "      if k > 26 or len(s) < k:  return 0\n",
    "      flag = collections.Counter(s[:k])\n",
    "      cnt = 0\n",
    "      if len(flag) == k:  cnt += 1\n",
    "      for i in range(k, len(s)):\n",
    "        flag[s[i-k]] -= 1\n",
    "        if flag[s[i-k]] == 0: del flag[s[i-k]]\n",
    "        flag[s[i]] += 1\n",
    "        if len(flag) == k:  cnt += 1\n",
    "      return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        if len(s) < k:\n",
    "            return 0 \n",
    "        count = 0\n",
    "        char_dict = {}\n",
    "        rev_dict = {}\n",
    "        l, r = 0, k-1\n",
    "        while r < len(s):\n",
    "            flag = True\n",
    "            if r == k-1:\n",
    "                while l<=r:\n",
    "                    char_dict[s[l]] = char_dict.get(s[l],0) + 1\n",
    "                    if char_dict[s[l]] >= 2:\n",
    "                        flag = False\n",
    "                    l+=1\n",
    "            else:\n",
    "                char_dict[s[r-k]] -= 1\n",
    "                char_dict[s[r]] = char_dict.get(s[r],0) + 1\n",
    "                if max(char_dict.values())>1:\n",
    "                    flag = False\n",
    "            if flag:\n",
    "                count += 1\n",
    "            r += 1\n",
    "        return count\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        res = 0\n",
    "        ch_set = Counter()\n",
    "        if n < k:\n",
    "            return res\n",
    "        for i in range(n):\n",
    "            ch_set[s[i]] += 1\n",
    "            if i >= k:\n",
    "                if ch_set[s[i - k]] == 1:\n",
    "                    del ch_set[s[i - k]]\n",
    "                else:\n",
    "                    ch_set[s[i - k]] -= 1\n",
    "            \n",
    "            if len(ch_set) == k:\n",
    "                res += 1\n",
    "            # print(i, ch_set,res)\n",
    "        return res\n",
    "            \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        res = 0\n",
    "        cur = ''\n",
    "        r,l = 0,0\n",
    "        while r<len(s):\n",
    "            cur += s[r]\n",
    "            if r-l+1>=k:\n",
    "                if len(cur)==len(set(cur)):\n",
    "                    res += 1\n",
    "                cur = cur[1:]\n",
    "                l += 1\n",
    "            r += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        #简单滑窗即可\n",
    "        n=len(s)\n",
    "        if k>n: return 0\n",
    "        mask=[0]*26\n",
    "        l,r=0,k-1\n",
    "        ans=0\n",
    "        for i in range(l,r+1):\n",
    "            cur=ord(s[i])-97\n",
    "            mask[cur]+=1\n",
    "        ans=1 if mask.count(1)==k else 0\n",
    "        while r+1<n:\n",
    "            mask[ord(s[l])-97]-=1\n",
    "            l+=1\n",
    "            r+=1\n",
    "            mask[ord(s[r])-97]+=1\n",
    "            if mask.count(1)==k: ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        if (k > 26):\n",
    "            return 0        \n",
    "        N = len(s)\n",
    "        left, right = 0, 0\n",
    "        res = 0\n",
    "        freq = [0] * 26\n",
    "        while right < N:\n",
    "            freq[ord(s[right]) - ord('a')] += 1\n",
    "            while freq[ord(s[right]) - ord('a')] > 1:\n",
    "                freq[ord(s[left]) - ord('a')] -= 1\n",
    "                left += 1\n",
    "            if right - left == k - 1:\n",
    "                res += 1\n",
    "                # 收缩窗口并从频率数组中移除最左边的字符\n",
    "                freq[ord(s[left]) - ord('a')] -= 1\n",
    "                left += 1\n",
    "            right += 1\n",
    "        return res\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        if k > len(s):\n",
    "            return 0\n",
    "        bucket = [False for _ in range(26)]\n",
    "        counter = 0\n",
    "        left = 0\n",
    "        for right in range(len(s)):\n",
    "            while bucket[ord(s[right])-ord(\"a\")]:\n",
    "                bucket[ord(s[left])-ord(\"a\")] = False\n",
    "                left += 1\n",
    "            bucket[ord(s[right])-ord(\"a\")] = True\n",
    "            if right - left + 1 >= k:\n",
    "                counter += 1\n",
    "        return counter\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeats(self, s:str) -> bool:\n",
    "        chars = set()\n",
    "        for char in s:\n",
    "            chars.add(char)\n",
    "        return len(chars)!=len(s)\n",
    "    \n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(s)-k+1):\n",
    "            sub = s[i:i+k]\n",
    "            if not self.repeats(sub):\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        ls = len(s)\n",
    "        out = 0\n",
    "\n",
    "        if ls >= k:\n",
    "            cur_set = []\n",
    "            for i in range(ls):\n",
    "                if not s[i] in cur_set:\n",
    "                    cur_set.append(s[i])\n",
    "                    if len(cur_set) == k:\n",
    "                        out += 1\n",
    "                        cur_set.pop(0)\n",
    "                else:\n",
    "                    start = cur_set.index(s[i])\n",
    "                    cur_set = cur_set[start+1:]\n",
    "                    cur_set.append(s[i])\n",
    "\n",
    "        return out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        i=0\n",
    "        res=0\n",
    "        while i<len(s)-k+1:\n",
    "            if len(set(s[i:i+k])) == k:\n",
    "                res+=1\n",
    "            i+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        count = 0\n",
    "        if len(s) < k:\n",
    "            return 0\n",
    "        for i in range(len(s)-k+1):\n",
    "            sk = dict(collections.Counter(s[i:i+k]))\n",
    "            if sum(sk.values()) == len(sk):\n",
    "                count += 1\n",
    "                # print(s[i:i+k])\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        i=0\n",
    "        res=0\n",
    "        while i<len(s)-k+1:\n",
    "            if len(set(s[i:i+k])) == k:\n",
    "                res+=1\n",
    "            i+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        n=len(s)\n",
    "        if k>n: return 0\n",
    "        mask=[0]*26\n",
    "        l,r=0,k-1\n",
    "        ans=0\n",
    "        for i in range(l,r+1):\n",
    "            cur=ord(s[i])-97\n",
    "            mask[cur]+=1\n",
    "        ans=1 if mask.count(1)==k else 0\n",
    "        while r+1<n:\n",
    "            mask[ord(s[l])-97]-=1\n",
    "            l+=1\n",
    "            r+=1\n",
    "            mask[ord(s[r])-97]+=1\n",
    "            if mask.count(1)==k: ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        r,l,res = 0,0,0\n",
    "        cur=''\n",
    "        while r<len(s):\n",
    "            cur += s[r]\n",
    "            if r-l+1>=k:\n",
    "                if len(set(cur))==len(cur):\n",
    "                    res+=1\n",
    "                cur=cur[1:]\n",
    "                l+=1\n",
    "            r+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        ans = 0\n",
    "        chars = set()\n",
    "        left = 0\n",
    "        right = 0\n",
    "\n",
    "        while right<len(s):\n",
    "            if s[right] not in chars:\n",
    "                chars.add(s[right])\n",
    "                if len(chars)==k:\n",
    "                    ans += 1\n",
    "                    chars.remove(s[left])\n",
    "                    left += 1\n",
    "                right += 1\n",
    "            else:\n",
    "                chars.remove(s[left])\n",
    "                left += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        l = len(s)\n",
    "        if l < k:\n",
    "            return 0\n",
    "        \n",
    "        hashmap = {}\n",
    "        count = 0\n",
    "        left = right = 0\n",
    "        while right < l:\n",
    "            if s[right] not in hashmap:\n",
    "                hashmap[s[right]] = 1\n",
    "            else:\n",
    "                hashmap[s[right]] += 1\n",
    "            while hashmap[s[right]] > 1:\n",
    "                hashmap[s[left]] -= 1\n",
    "                if hashmap[s[left]] == 0:\n",
    "                    del hashmap[s[left]]\n",
    "                left += 1\n",
    "            if right - left + 1 >= k:\n",
    "                count += 1\n",
    "            right += 1\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        ans = 0\n",
    "        chars = set()\n",
    "        left = 0\n",
    "        right = 0\n",
    "\n",
    "        while right<len(s):\n",
    "            if s[right] not in chars:\n",
    "                chars.add(s[right])\n",
    "                if len(chars)<k:\n",
    "                    right += 1\n",
    "                elif len(chars)==k:\n",
    "                    ans += 1\n",
    "                    chars.remove(s[left])\n",
    "                    left += 1\n",
    "                    right += 1\n",
    "            else:\n",
    "                left += 1\n",
    "                right = left\n",
    "                chars.clear()\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        if k > len(s):\n",
    "            return 0\n",
    "        res = 0\n",
    "        for i in range(len(s)):\n",
    "            charSet = set()\n",
    "            for char in s[i : i + k]:\n",
    "                charSet.add(char)\n",
    "            if len(charSet) == k:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        i=0\n",
    "        res=0\n",
    "        while i<len(s)-k+1:\n",
    "            if len(set(s[i:i+k])) == k:\n",
    "                res+=1\n",
    "            i+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        r,l,res = 0,0,0\n",
    "        cur=''\n",
    "        while r<len(s):\n",
    "            cur += s[r]\n",
    "            if r-l+1>=k:\n",
    "                if len(set(cur))==r-l+1:\n",
    "                    res+=1\n",
    "                cur=cur[1:]\n",
    "                l+=1\n",
    "            r+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        ans = 0\n",
    "        vis = set()\n",
    "        j = 0\n",
    "        for i, x in enumerate(s):\n",
    "            while x in vis:\n",
    "                vis.remove(s[j])\n",
    "                j += 1\n",
    "            vis.add(x)\n",
    "            while len(vis) > k:\n",
    "                vis.remove(s[j])\n",
    "                j += 1\n",
    "            if len(vis) == k:\n",
    "                ans += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        num = 0\n",
    "        hashmap = {}\n",
    "        if k>len(s):\n",
    "            return 0\n",
    "        start = 0\n",
    "        for end in range(len(s)):\n",
    "            tail = s[end]     \n",
    "            while tail in hashmap:\n",
    "                head = s[start]\n",
    "                del hashmap[head]\n",
    "                start+=1\n",
    "            if tail not in hashmap:\n",
    "                hashmap[tail] = 1\n",
    "            \n",
    "            if len(hashmap)==k:\n",
    "                num+=1\n",
    "                head = s[start]\n",
    "                del hashmap[head]\n",
    "                start+=1\n",
    "        return num\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        l = len(s)\n",
    "        if l < k or k > 26:\n",
    "            return 0\n",
    "        \n",
    "        freq = [0] * 26\n",
    "        count = 0\n",
    "        left = right = 0\n",
    "        while right < l:\n",
    "            num = ord(s[right]) - ord('a')\n",
    "            freq[num] += 1\n",
    "            while freq[num] == 2:\n",
    "                numl = ord(s[left]) - ord('a')\n",
    "                freq[numl] -= 1\n",
    "                left += 1\n",
    "            if right - left + 1 == k:\n",
    "                count += 1\n",
    "                numl = ord(s[left]) - ord('a')\n",
    "                freq[numl] -= 1\n",
    "                left += 1\n",
    "            right += 1\n",
    "        return count\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        def check(letters):\n",
    "            return sum([i > 0 for i in letters])\n",
    "        \n",
    "        if k > 26: return 0\n",
    "        letters, res = [0] * 26, 0\n",
    "        l, n = 0, len(s)\n",
    "        for r in range(n):\n",
    "            letters[ord(s[r]) - ord('a')] += 1\n",
    "            if r - l + 1 == k:\n",
    "                if check(letters) == k:\n",
    "                    res += 1\n",
    "                letters[ord(s[l]) - ord('a')] -= 1\n",
    "                l += 1\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        if len(s) < k or k > 26:\n",
    "            return 0\n",
    "        \n",
    "        start = end = ans = 0\n",
    "        cnt = collections.defaultdict(int)\n",
    "\n",
    "        while end < len(s):\n",
    "            cnt[s[end]] += 1\n",
    "            while cnt[s[end]] == 2:\n",
    "                cnt[s[start]] -= 1\n",
    "                if cnt[s[start]] == 0:\n",
    "                    del cnt[s[start]]\n",
    "                start += 1\n",
    "            if len(cnt) >= k:\n",
    "                ans += 1\n",
    "            end += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        ans = 0\n",
    "        if k > len(s): return ans\n",
    "        def is_no_repeat(s1):\n",
    "            my_set = set(s1)\n",
    "            return len(my_set) == k\n",
    "        for i in range(len(s) - k + 1):\n",
    "            if is_no_repeat(s[i:i + k]): ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        ans = 0\n",
    "        window = collections.defaultdict(int)\n",
    "        for i in range(len(s)):\n",
    "            window[s[i]] += 1\n",
    "            if i >= k - 1:\n",
    "                if len(window) == k:\n",
    "                    ans += 1\n",
    "                window[s[i - k + 1]] -= 1\n",
    "                if window[s[i - k + 1]] == 0:\n",
    "                    window.pop(s[i - k + 1])\n",
    "        return ans\n",
    "                \n",
    "        # window = Counter()\n",
    "        # valid = 0\n",
    "        # l, r = 0, 0\n",
    "        # n = len(s)\n",
    "        # res = 0\n",
    "        # while r < n:\n",
    "        #     c = s[r]\n",
    "        #     r += 1\n",
    "        #     if window[c] == 0:\n",
    "        #         valid += 1\n",
    "        #     window[c] += 1\n",
    "        #     while r - l >= k:\n",
    "        #         if valid == k:\n",
    "        #             res += 1\n",
    "        #         d = s[l]\n",
    "        #         l += 1\n",
    "        #         window[d] -= 1\n",
    "        #         if not window[d]:\n",
    "        #             valid -= 1\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        l = len(s)\n",
    "        if l < k:\n",
    "            return 0\n",
    "        \n",
    "        hashmap = {}\n",
    "        count = 0\n",
    "        left = right = 0\n",
    "        while right < l:\n",
    "            if s[right] not in hashmap:\n",
    "                hashmap[s[right]] = 1\n",
    "            else:\n",
    "                hashmap[s[right]] += 1\n",
    "            while hashmap[s[right]] > 1:\n",
    "                hashmap[s[left]] -= 1\n",
    "                if hashmap[s[left]] == 0:\n",
    "                    del hashmap[s[left]]\n",
    "                left += 1\n",
    "            if len(hashmap) >= k:\n",
    "                count += 1\n",
    "            right += 1\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        max_s,hashmap=0,{}\n",
    "        start=0\n",
    "        for i in range(len(s)):\n",
    "            hashmap[s[i]]=hashmap.get(s[i],0)+1\n",
    "            while hashmap[s[i]]>1:\n",
    "                hashmap[s[start]]-=1\n",
    "                if hashmap[s[start]]==0:\n",
    "                    del hashmap[s[start]]\n",
    "                start+=1\n",
    "            if len(hashmap)>=k:\n",
    "                max_s+=1\n",
    "        return max_s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 哈希+滑动窗口\n",
    "    def numKLenSubstrNoRepeats1(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        if n < k or k > 26:\n",
    "            return 0\n",
    "\n",
    "        count = [0]*26\n",
    "        ans = 0\n",
    "        for i in range(k):\n",
    "            count[ord(s[i])-ord('a')] += 1\n",
    "\n",
    "        if max(count) <= 1:\n",
    "            ans += 1\n",
    "\n",
    "        for i in range(k, n):\n",
    "            count[ord(s[i]) - ord('a')] += 1\n",
    "            count[ord(s[i-k]) - ord('a')] -= 1\n",
    "            if max(count) <= 1:\n",
    "                ans += 1\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "    # 定长双指针\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        if n < k or k > 26:\n",
    "            return 0\n",
    "        \n",
    "        j = 0\n",
    "        pre = set()\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            while j < n and j - i < k and s[j] not in pre:\n",
    "                pre.add(s[j])\n",
    "                j += 1\n",
    "            \n",
    "            if j - i == k:\n",
    "                ans += 1\n",
    "            \n",
    "            pre.discard(s[i])\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        if k <= 0 or len(s) < k:\n",
    "            return 0\n",
    "        \n",
    "        left = 0\n",
    "        right = left + k - 1\n",
    "        count = 0\n",
    "\n",
    "        hashmap = {}\n",
    "        for i in range(k):\n",
    "            hashmap[s[i]] = hashmap.get(s[i], 0) + 1\n",
    "\n",
    "        while right < len(s):\n",
    "            if len(hashmap) == k:\n",
    "                count += 1\n",
    "            \n",
    "            right += 1\n",
    "            if right > len(s) - 1:\n",
    "                break\n",
    "            \n",
    "            hashmap[s[right]] = hashmap.get(s[right], 0) + 1\n",
    "            hashmap[s[left]] -= 1\n",
    "            if hashmap[s[left]] <= 0:\n",
    "                del hashmap[s[left]]\n",
    "            \n",
    "            left += 1\n",
    "        \n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        num = 0\n",
    "        hashmap = {}\n",
    "        if k>len(s):\n",
    "            return 0\n",
    "        start = 0\n",
    "        for end in range(len(s)):\n",
    "            tail = s[end]     \n",
    "            while tail in hashmap:\n",
    "                head = s[start]\n",
    "                del hashmap[head]\n",
    "                start+=1\n",
    "            if tail not in hashmap:\n",
    "                hashmap[tail] = 1\n",
    "            \n",
    "            if len(hashmap)==k:\n",
    "                num+=1\n",
    "                head = s[start]\n",
    "                del hashmap[head]\n",
    "                start+=1\n",
    "        return num\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        size = len(s)\n",
    "        if size < k:\n",
    "            return 0\n",
    "        left, right = 0, k - 1\n",
    "        res = 0\n",
    "        while right < size:\n",
    "            sets = set(s[left:right + 1])\n",
    "            if len(sets) == k:\n",
    "                res += 1\n",
    "            left += 1\n",
    "            right += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, S: str, K: int) -> int:\n",
    "        n = len(S)\n",
    "        if K > n:\n",
    "            return 0\n",
    "        #初始化一个字典\n",
    "        char_cnt = defaultdict(int)\n",
    "        kind = 0#滑动窗口内的字符种类\n",
    "        for i in range(K): #第一个滑动窗口内的情况,\n",
    "            #新元素，则种类+1\n",
    "            if S[i] not in char_cnt:\n",
    "                kind += 1\n",
    "            char_cnt[S[i]] = char_cnt.get(S[i],0)+1\n",
    "            #char_cnt[S[i]] += 1\n",
    "        res = 1 if kind==K else 0\n",
    "        #第二个窗口以后的情况\n",
    "        for R in range(K, n):       \n",
    "            if char_cnt[S[R]] == 0:     #进R\n",
    "                kind += 1\n",
    "            char_cnt[S[R]] += 1\n",
    "            char_cnt[S[R-K]] -= 1       #弹L\n",
    "            if char_cnt[S[R-K]] == 0:#如果这个健减一之后的值为零，\n",
    "                kind -= 1# 那么种类数也相应减一\n",
    "            \n",
    "            if kind == K:               #更新res\n",
    "                res += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        left, n = 0, len(s)\n",
    "        if n < k:\n",
    "            return 0\n",
    "        s = list(s)\n",
    "        hm = collections.defaultdict(int)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            cur = s[i]\n",
    "            hm[cur] += 1\n",
    "            while left < i and hm[cur] > 1:\n",
    "                hm[s[left]] -= 1\n",
    "                if hm[s[left]] == 0:\n",
    "                    hm.pop(s[left])\n",
    "                left += 1\n",
    "\n",
    "            if i - left + 1 >= k:\n",
    "                res += 1\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        from collections import defaultdict\n",
    "        left, right = 0, 0\n",
    "        windows = defaultdict(list)\n",
    "        n = len(s)\n",
    "        res = 0\n",
    "        double = None\n",
    "\n",
    "        while right < n:\n",
    "            curEle = s[right]\n",
    "            right += 1\n",
    "            windows[curEle].append(right-1)\n",
    "            if len(windows[curEle]) >=2:\n",
    "                double = curEle\n",
    "            print(right,left,windows)\n",
    "            while double or right - left > k:\n",
    "                deltEle = s[left]\n",
    "                left += 1\n",
    "                windows[deltEle].pop(0)\n",
    "                if windows[deltEle] == list():\n",
    "                    windows.pop(deltEle)\n",
    "                if double and double == deltEle:\n",
    "                    double = None\n",
    "                    \n",
    "            if right - left == k:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        if len(s) < k:\n",
    "            return 0\n",
    "        c = 0\n",
    "        for i in range(len(s)-k+1):\n",
    "            sub = s[i:i+k]\n",
    "            cc = [sub.count(sub[j]) for j in range(k)]\n",
    "            # print(max(cc))\n",
    "            if max(cc) > 1:\n",
    "                continue\n",
    "            else: c +=1\n",
    "            # a=0\n",
    "        # print(s[i:i+k])\n",
    "        return c\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:\n",
    "        return len([i for i in range(len(s)-k+1) if len(set(s[i:i+k])) == k])\n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
